<?php
// Boggle board is a 4*4 2D array of letters.
// Word is valid if made up with adjacent letters.
// Adjacent can be horizontal, vertical or diagonal
//
// Question: Testing of a 4 letter word

//
// Note: Sometimes there are more options for a letter
// Use array push and pop to store the solution and kick out used blocks

$boggle = array(
	array('S', 'M', 'E', 'F'),
	array('R', 'A', 'T', 'D'),
	array('L', 'O', 'N', 'I'),
	array('K', 'A', 'F', 'B'),
);

$words = array("MATE", "TONE", "FIND", "LATE", "KAFA");

echo "Searching boggle:<br/>";
for( $posY=0; $posY<4; $posY++ ){
	for( $posX=0; $posX<4; $posX++ ){
		echo $boggle[$posY][$posX]."   ";
	}
	echo "<br/>";
}

foreach( $words as $word ){
	$solution = array();
	if( checkBoggleBoard($word, $boggle) ){
		echo "$word is in the boggle.<br/>";
		var_dump( $solution );
	}
	else {
		echo "$word is not in the boggle.<br/>";
	}
}

function searchWord( $word, $boggle, $startY, $startX ){

	global $solution;

	$adjacent_positions = array(
		array(-1, -1),
		array(-1,  0),
		array(-1,  1),
		array( 0, -1),
		array( 0,  1),
		array( 1, -1),
		array( 1,  0),
		array( 1,  1),
	);

	$length = strlen( $word );

	$letter = $word[0];

	foreach( $adjacent_positions as $adjacent ){
		$search_y = $startY + $adjacent[0];
		$search_x = $startX + $adjacent[1];

		if( 0 > $search_x || 4 <= $search_x ||
			0 > $search_y || 4 <= $search_y ){

			// No such block
			continue;
		}

		$isUsed = false;
		foreach( $solution as $used_block ){
			if( $used_block[1] == $search_x &&
				$used_block[0] == $search_y ){

				// No such block
				$isUsed = true;
			}
		}

		if( $isUsed ){
			continue;
		}

		if( $boggle[$search_y][$search_x] == $letter ){
			if( 1 == $length ){
				array_push( $solution, array($search_y, $search_x) );
				return true;
			}
			else {
				$word = substr($word, 1);
				array_push( $solution, array($search_y, $search_x) );
				if( searchWord( $word, $boggle, $search_y, $search_x) ){
					return true;
				}
				else {
					// Wrong direction
					array_pop( $solution );
					return false;
				}
			}
		}
	}

	// Return array of all possible results
	return false;
}

// Check if a 4-letter word is inside the boggle board
function checkBoggleBoard( $word, $boggle ){

	global $solution;

	if( 4 != strlen($word) ){
		return false;
	}

	// Starting from the first letter
	$cur_pos = 0;
	$cur_letter = $word[ $cur_pos ];

	$found = false;

	$start_pos = array();

	// Locate the first letter
	for( $posY=0; $posY<4; $posY++ ){
		for( $posX=0; $posX<4; $posX++ ){
			if( $cur_letter == $boggle[$posY][$posX] ){
				// Found!
				$found = true;
				$start_pos[] = array( $posY, $posX );
			}
		}
	}

	if( !$found ){
		return false;
	}

	// Start on every possible starting point
	$word = substr($word, 1);

	foreach ($start_pos as $start){
		array_push( $solution, array($start[0], $start[1]) );
		if( searchWord( $word, $boggle, $start[0], $start[1]) ){
			return true;
		}
		array_pop( $solution );
	}

	return false;
}